Present day ultra-large-scale integration (ULSI) circuits may include hundreds of thousands or millions of interconnected active electronic devices on an integrated circuit chip. The large capital investment required to fabricate and test large scale integrated circuits prior to sale to a customer and the difficulty, expense and loss of goodwill associated with reworking and replacing integrated circuits which fail to operate as planned, have increased the need to accurately characterize the electrical behavior of integrated circuits prior to their manufacture.
Moreover, now that submicron and deep-submicron (0.5 .mu.m and below) technologies have begun to dominate silicon chip manufacturing and the prospect of million-plus-gate chips operating at clock rates of 100 MHz has become a reality, fundamental changes have had to be made to conventional integrated circuit design methodologies and the electronic design automation (EDA) tools based thereon. To meet the challenges posed by such large-scale circuits, techniques have been developed to represent integrated circuit designs at various levels of abstraction. According to these techniques, a design may be represented by a high-level behavioral description, as a schematic (or, equivalently, a netlist), or by geometric layout data which describes patterns of substances to be deposited on a semiconductor substrate (i.e., a layout). Other techniques for managing such highly integrated circuit designs include hierarchical design techniques. Here, a particular design is partitioned into functional cells and cells-within-cells, etc., so that at a given level of hierarchy the design may be analyzed as a set of cells and their respective interconnections, without being concerned with the details of the contents of the cells (e.g., subcells within each cell).
These techniques can be essential to the efficient performance of computer-assisted integrated circuit design verification. Such verification may include operations to perform layout versus schematic comparison (LVS) using computer-based design tools. As will be understood by those skilled in the art, tools to perform layout versus schematic comparison may include circuit extraction software to extract electrical schematics containing nets and devices from layout designs. An extracted electrical schematic may then be compared to an original schematic to determine functional equivalence between the original integrated circuit schematic and the integrated circuit layout. One difficulty associated with the performance of these operations may be caused by a dissimilarity in the labeling of nets and devices in the extracted schematic relative to the original schematic. Moreover, because it is not a trivial task to establish one-to-one correspondence between the components of the extracted schematic and the original schematic, the primary function of LVS software is to determine the correspondence or lack of correspondence between the original and extracted schematics which may be represented as a schematic netlist and layout netlist, respectively.
Conventional methods for determining correspondence between an original electrical schematic (e.g., schematic netlist) and a schematic which has been extracted from a layout (e.g., layout netlist) are described in U.S. Pat. No. 5,249,133 to Batra entitled "Method for the Hierarchical Comparison of Schematics and Layouts of Electronic Components"; U.S. Pat. No. 5,463,561 to Razdan entitled "High Capacity Netlist Comparison"; and U.S. Pat. No. 5,243,538 to Okuzawa et al. entitled "Comparison and Verification System for Logic Circuits and Method Thereof." Another conventional method for determining correspondence includes operations to represent the original schematic and extracted schematic as respective bipartite graphs having vertices which represent nets and devices. LVS software is then used to determine an isomorphism between the bipartite graphs.
The unambiguous determination of isomorphism between two arbitrary graphs may be a computationally intractable problem. To address this problem, heuristic methods for identifying graph isomorphisms with acceptable reliability and efficiency for ULSI designs have been developed. One generally established heuristic method is an iterative graph-coloring method described in articles by C. Ebeling and O. Zajicek entitled "Validating VLSI Circuit Layout By Wirelist Comparison," Proceedings of ICCAD, pp. 172-173 (1983); and by C. Ebeling entitled "Gemini II: A Second Generation Layout Validation Program," IEEE ICCAD-88, Digest of Technical Papers, pp. 322-325, November 7-10 (1988), the disclosures of which are hereby incorporated herein by reference. As described in these articles, an integer (color) is assigned to each vertex of a bipartite graph of the original schematic and extracted schematic, based on a graph invariant such as "number of neighbors" (i.e., adjacent vertices). Each vertex is iteratively recolored as a function of the colors of its neighbors, until the maximum number of unique colors is achieved. Because these operations are independent of labeling, equivalent original and extracted schematics will be represented by the same set of colors. A one-to-one correspondence may then be achieved by simply matching up each vertex in the schematic with a vertex in the layout of the same color.
Unfortunately, some circuits may exhibit symmetry which may cause different vertices to receive the same color because the "neighborhoods" associated with these vertices look alike. Thus, when two or more vertices have the same color, ambiguities in selecting matching vertices may arise. Typically, this situation is handled by making a guess as to which ones of the same colored vertices in the extracted schematic correspond to the same colored vertices in the original schematic, then assigning new colors to the matched vertices and then recoloring. If the guess was incorrect, a number of vertices may fail to match when the matching is applied at the next level of hierarchy, even though an alternate guess might have resulted in a complete one-to-one mapping.
For example, the AND-OR-INVERT (AOI) cell of FIG. 1 exhibits a number of symmetries with respect to input A because input A may be independently swapped with input B or input A may be swapped with input C if and only if input B is swapped with input D. Similar symmetries also exist with respect to inputs B, C and D. FIG. 2 illustrates an original electrical schematic (S1) of the AOI and an extracted electrical schematic (L1) of the AOI which will be referred to as "the layout". FIG. 3 illustrates an electrical schematic design (S2) which contains the AOI schematic cell (S1) of FIG. 2 as a subcell and a layout design (L2) which contains the AOI layout (L1) of FIG. 2 as a subcell. As will be understood by those skilled in the art, verification of the designs of FIG. 3 will only be concerned with the mapping of ports (W, X, Y, Z) of the layout L1 of FIG. 2 to the ports (Q, R, S, T) of the schematic S2 of FIG. 2. However, because the symmetry of the design will cause ports A, B, C, D to acquire the same color, a conventional LVS tool may make an arbitrary mapping which may be incorrect (e.g., Q.fwdarw.W, R.fwdarw.Y, S.fwdarw.X, T.fwdarw.Z). A consequence of this arbitrary mapping may be manifested at the next level of hierarchy. For example, as illustrated by FIG. 3, an incorrect choice in the mapping of S1 to L1 (i.e., the child cells) may cause S2 and L2 (i.e., the parent cells) to be reported as nonequivalent. Here, devices D1-D4 are distinct devices that are connected between the ports of the AOI "child" cell and the ports of the "parent" cell. Thus, LVS software may report a mismatch between an original schematic and an extracted schematic/layout, even though it is possible to make assignments among symmetric vertices that will result in a match. Typically, a consequence of this limitation in LVS software is that the software user must manually intervene by providing the LVS software with specific assignments to resolve ambiguities due to symmetry. Since it is not always clear where an erroneous guess was made, such manual intervention may be time consuming. For highly symmetric designs such as memories and gate arrays, these limitations may significantly reduce the utility of LVS software.
To address some of these limitations associated with conventional verification tools, an LVS software tool 100 has been developed to determine equivalency between an integrated circuit schematic and an integrated circuit layout, using the operations 102-114 illustrated by the flow diagram of FIG. 4. This LVS software tool is a commercially available product from the assignee of the present application, Avant! Corporation of Sunnyvale, Calif. This software product, which is marketed under the tradename Hercules.TM., is more fully described in an instruction manual by the same name, Release 2.1, January (1997), the disclosure of which is hereby incorporated herein by reference. In particular, the LVS software tool of FIG. 4 can perform the operations of generating a hierarchical electrical schematic netlist having at least one parent cell and a plurality of child cells in the parent cell, Block 102, and extracting a corresponding integrated circuit layout as a hierarchical layout netlist, Block 104. An operation is also performed to generate at least one color symmetrizing matrix corresponding to a child cell in the schematic netlist, Block 106. Here, the child cell may have a number of symmetries which, when taken alone or in combination, may result in a number of electrically equivalent permutations of the child cell. As illustrated by Block 108, operations are then performed to generate schematic and layout graphs of the parent cells in the schematic and layout netlists, respectively. These graphs are similar to the above-described bipartite graphs. The vertices in the schematic graph are then colored and a first color symmetry vector is generated for a child cell in the schematic graph. Similarly, the vertices in the layout graph are colored and a second color symmetry vector is generated for a child cell in the layout graph, Block 110.
An operation is then performed to determine an equivalency between the colors of the vertices in the schematic and layout graphs based on a selected permutation of the child cell in the layout graph, Block 112, and then an operation is performed to determine a vector equivalency between a product of the color symmetrizing matrix and the first color vector and a product of the color symmetrizing matrix and the second color vector, Block 114. Finally, a membership test is automatically performed at Block 116 to determine whether the selected permutation of the child cell can be derived from the valid symmetries associated with that child cell. As described in a textbook authored by G. Butler, entitled Fundamental Algorithms for Permutation Groups, Springer-Verlag, p. 144 (1991), a Furst-Hopcroft-Luks version of a Schreier-Sims method may be performed. Unfortunately, although the software tool of FIG. 4 typically requires no human intervention, provides adequate performance and works well with most designs exhibiting symmetry, the automatic performance of membership test to validate the accuracy of the matched layout and schematic may incur an unduly large computational expense and limit the applicability of the above software to large integrated circuit designs having large degrees of symmetry.
Thus, notwithstanding the above described attempts at providing LVS verification tools, there continues to be a need to provide verification tools which have the capability of automatically resolving ambiguities in symmetric circuits. Such tools should be conservative in the identification of graph isomorphism, in the sense that if any ambiguities remain after the verification operations are performed, a nonisomorphism result should be generated and the circuits should be designated as non-equivalent even if they may be equivalent. This is because the penalty for erroneously identifying equivalent circuits as nonequivalent (i.e., manual intervention by the user) is far less onerous than the penalty for misidentifying non-equivalent circuits as equivalent (i.e., the expense of prototyping and manufacturing an incorrect design).